﻿#define _CRT_SECURE_NO_WARNINGS 1
//给定一个数组，包含从 1 到 N 所有的整数，但其中缺了两个数字。你能在 O(N) 时间内只用 O(1) 的空间找到它们吗？
//以任意顺序返回这两个数字均可。

//eg：输入：[1] 输出：[2, 3]
#include <iostream>
#include <vector>
using namespace std;

//思路：丢失的数字+只出现一次的数字III结合
vector<int> missingTwo(vector<int>& nums)
{
	// 1. 将所有的数异或在⼀起
	int tmp = 0;
	for (auto x : nums) tmp ^= x;
	for (int i = 1; i <= nums.size() + 2; i++) tmp ^= i;
	// 2. 找出 a，b 中⽐特位不同的那⼀位
	int diff = 0;
	while (1)
	{
		if (((tmp >> diff) & 1) == 1) break;
		else diff++;
	}
	// 3. 根据 diff 位的不同，将所有的数划分为两类来异或
	int a = 0, b = 0;
	for (int x : nums)
		if (((x >> diff) & 1) == 1) b ^= x;
		else a ^= x;
	for (int i = 1; i <= nums.size() + 2; i++)
		if (((i >> diff) & 1) == 1) b ^= i;
		else a ^= i;

	return { a, b };
}

int main()
{
	vector<int> nums = { 1 };
	vector<int> an = missingTwo(nums);
	for (auto a : an)
	{
		cout << a << ' ';
	}
	cout << endl;

	return 0;
}